\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{subfigure}
\usepackage{float}

\title{五则运算计算器的实现}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle

\section{项目设计思路}

本项目要求完成五则运算计算器的程序设计,在给定输入的情况下,根据运算律计算正确的结果,具体要求包括:
(1)求解任意长度的含加减乘除和乘方运算的表达式结果;
(2)允许浮点数计算和带括号计算;
(3)能够检测错误输入并给出错误信息.

采取的主要设计思路是利用中缀表达式转后缀表达式,生成表达式树,并通过中序遍历递归计算. 整个程序通过基类 \verb|Expression| 和两个派生类 \verb|Constant| 和 \verb|Operation| 实现, \verb|map<string, double>| 处理未知数, 同时利用了两个功能较为重要的函数 \verb|double Evaluate()| 和 \verb|void strToTree()|.
\begin{figure}[H]
        \centering
	\includegraphics[width = 0.5\linewidth]{./Figure/figure.png}
	\caption{程序设计结构}
        \label{Figure}
\end{figure}

函数 \verb|Evaluate| 由基类定义,两个派生类重写,其功能是返回单步五则运算结果, 其中可判断除数为零时的报错. 在 \verb|Constant| 类中直接返回. 函数 \verb|strToTree| 的功能是通过递归算法将字符串转换为表达式树, 同时可利用记录括号的变量 \verb|brackets| 判断括号不匹配的情况,具体实现如下:
\begin{verbatim}
//s起始位置，t结束位置
Expression *strToTree(string str, int s, int t)
{
	//去除包含整个当前表达式的括号
	while (s <= t&&str[s] == '('&&str[t] == ')')s++, t--;
	if (s > t)
		return new Constant(0);
	//findLetter找到字母，用以判断是否为未知数
	//findChar找到字符，用以判断是否存在运算符
	bool findChar = false;
	//括号标记
	int brackets = 0;
	//lastPS最后的加减法
	//lastMD最后的乘除
	int lastPS = -1, lastMD = -1;

	for (int i = s; i <= t; i++)
	{
		//当前位置不是常数
		if (str[i] != '.' && (str[i]<'0' || str[i]>'9'))
		{
				//不是常数，就是运算符或是不合法输入
				findChar = true;
				switch (str[i])
				{
				case '(' :
					brackets++;
					break;
				case ')' :
					brackets--;
					break;
				//更新最后加减法的位置
				case '+' :
				case '-' :
					if (!brackets){
						 lastPS = i;
					}
					break;
				//更新最后乘除法的位置
				case '*' :
				case '/' :
				case '^' :
					if (!brackets){
						lastMD = i;
					}
					break;
				default :
					cout << "错误: 非法运算符" << endl;
					return nullptr;
				}
		}
	}
	//括号不匹配
	if (brackets != 0){
		cout << "错误: 括号不匹配" << endl;
		exit(0);
	}
	//从s到t都是常数
	if (findChar == false){
		return new Constant(stod(str.substr(s, t - s + 1)));
	}
	//从s到t是个运算
	//没有加减就用乘除
	if (lastPS == -1){
		lastPS = lastMD;
	}

	//乘除法优先级更高因此优先在加减处分割,即最后算加减法
	//递归
	return new Operation(strToTree(str, s, lastPS - 1), str[lastPS], strToTree(str, lastPS + 1, t));
}
\end{verbatim}



\section{测试流程说明}

(1)测试该计算器能正常运行并输出正确结果, 如图2所示:
\begin{figure}[H]
        \centering
        \includegraphics{./Figure/figure1.png}
        \caption{测试算法正确性}
        \label{Figure 1}
\end{figure}

(2)测试检测括号不匹配时的错误输入并给出错误信息, 如图3所示:
\begin{figure}[H]
        \centering
        \includegraphics{./Figure/figure2.png}
        \caption{错误:括号不匹配}
        \label{Figure 2}
\end{figure}

(3)测试检测除数为零时的错误输入并给出错误信息, 如图4所示:
\begin{figure}[H]
        \centering
        \includegraphics{./Figure/figure3.png}
        \caption{错误:除数为零}
        \label{Figure 3}
\end{figure}


(4)内存泄漏检查结果如下:
\begin{verbatim}
==2558== 
==2558== HEAP SUMMARY:
==2558==     in use at exit: 0 bytes in 0 blocks
==2558==   total heap usage: 3 allocs, 3 frees, 74,752 bytes allocated
==2558== 
==2558== All heap blocks were freed -- no leaks are possible
==2558== 
==2558== For counts of detected and suppressed errors, rerun with: -v
==2558== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
\end{verbatim}

\end{document}
